package com.xigua.bfs;

import java.util.*;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description:给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
 *每一步，你可以从下标 i 跳到下标：
 *i + 1 满足：i + 1 < arr.length
 *i - 1 满足：i - 1 >= 0
 *j 满足：arr[i] == arr[j] 且 i != j
 *请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。
 *注意：任何时候你都不能跳到数组外面。
 * @date 2022/1/2110:15
 */
public class _1345_跳跃游戏 {

    public int minJumps(int[] arr) {
        Map<Integer, List<Integer>> idxSampeValue = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            idxSampeValue.putIfAbsent(arr[i], new ArrayList<>());
            idxSampeValue.get(arr[i]).add(i);
        }

        Set<Integer> visitedIndex = new HashSet<>();
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{0, 0});
        visitedIndex.add(0);
        while (!queue.isEmpty()) {
            int[] idxStep = queue.poll();
            int idx = idxStep[0], step = idxStep[1];
            if (idx == arr.length - 1) return step;
            int v =arr[idx];
            step++;
            if (idxSampeValue.containsKey(v)){
                for (int i : idxSampeValue.get(v)) {
                    if (visitedIndex.add(i)){
                        queue.offer(new int[]{i,step});
                    }
                }
                idxSampeValue.remove(v);
            }
            if (idx+1 < arr.length &&visitedIndex.add(idx+1)){
                queue.offer(new int[]{idx+1,step});
            }
            if (idx -1 >=0 &&visitedIndex.add(idx-1)){
                queue.offer(new int[]{idx-1,step});
            }

        }
        return -1;
    }
}
